package com.dong.arithmetic.sort;

import java.util.Arrays;

/**
 * 快速排序
 * 原理：高位低位交叉对比，把数组分成两部分，左边都小于某个元素A，右边都大于A。
 *
 * @author jianyang206881
 * @date 2018/6/6
 */
public class QuickSort {

    /**
     * 快速排序
     *
     * @param arrs       数组
     * @param leftIndex  左边下标
     * @param rightIndex 右边下标
     */
    public void quickSort(int[] arrs, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            // 当前下标
            int currentIndex = leftIndex;
            int startIndex = leftIndex;
            int endIndex = rightIndex;

            while (leftIndex < rightIndex) {

                // 从右边开始判断，如果比当前数大，下标左移一位
                while (rightIndex > currentIndex && arrs[rightIndex] > arrs[currentIndex]) {
                    rightIndex--;
                }

                if (rightIndex > currentIndex) {
                    this.swap(arrs, currentIndex, rightIndex);
                    currentIndex = rightIndex;
                }

                // 从左边开始判断，如果比当前数小，下标右移一位
                while (leftIndex < currentIndex && arrs[leftIndex] < arrs[currentIndex]) {
                    leftIndex++;
                }

                if (leftIndex < currentIndex) {
                    this.swap(arrs, currentIndex, leftIndex);
                    currentIndex = leftIndex;
                }
            }
            this.quickSort(arrs, currentIndex + 1, endIndex);
            this.quickSort(arrs, startIndex, currentIndex - 1);
        }
    }

    /**
     * 把下标对应的两个数位置交换
     *
     * @param arrs       数组
     * @param oneIndex   下标
     * @param otherIndex 下标
     */
    private void swap(int[] arrs, int oneIndex, int otherIndex) {
        // 临时变量，用于交换时使用
        int tmp = arrs[oneIndex];
        arrs[oneIndex] = arrs[otherIndex];
        arrs[otherIndex] = tmp;
    }

    public static void main(String[] args) {
        int[] arrs = new int[]{2, 1, 4, 5, 8, 7, 6, 3, 9, 0};

        new QuickSort().quickSort(arrs, 0, arrs.length - 1);

        Arrays.stream(arrs).forEach(value -> System.out.print(value + ","));

    }

}
